package com.sunny.t3;

/**
 * 二叉树中序转双向链表
 */
public class Main {

    LinkedNode prev, head;

    public static void main(String[] args) {

        Main main = new Main();

        TreeNode root = new TreeNode(1);
        TreeNode l1 = new TreeNode(2);
        root.left = l1;
        TreeNode r1 = new TreeNode(3);
        root.right = r1;
        TreeNode l2 = new TreeNode(5);
        l1.right = l2;
        TreeNode r2 = new TreeNode(6);
        r1.left = r2;

        LinkedNode head = main.solve(root);

        main.printLinkedNode(head);

    }

    public void printLinkedNode(LinkedNode head){
        LinkedNode node = head;
        while (null != node){
            System.out.print(node.val+" ");
            node = node.next;
        }
        System.out.println();
    }

    public LinkedNode solve(TreeNode root){
        if(null == root)
            return head;
        dfs(root);
        return head;
    }

    public void dfs(TreeNode node){

        if(null != node.left){
            dfs(node.left);
        }
        LinkedNode linkedNode = new LinkedNode(node.val);
        if(null != prev){
            prev.next = linkedNode;
            linkedNode.prev = prev;
            prev = linkedNode;
        }else{
            prev = linkedNode;
            head = linkedNode;
        }
        if(null != node.right){
            dfs(node.right);
        }

    }

}

class TreeNode{
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }
}

class LinkedNode{
    int val;
    LinkedNode prev, next;

    public LinkedNode(int val) {
        this.val = val;
    }
}